package Hot100.Heap;

import java.text.DecimalFormat;
import java.util.PriorityQueue;
import java.util.Queue;

public class MedianFinder {
    Queue<Integer> A,B;

    public MedianFinder() {
        //初始化大顶堆和小顶堆
        A = new PriorityQueue<>((x,y) -> (y - x));//大顶堆
        B = new PriorityQueue<>();//小顶堆
    }

    public void addNum(int num) {
        if(A.size() == B.size()){
            A.add(num);
            B.add(A.poll());
        }else {
            B.add(num);
            A.add(B.poll());
        }
    }

    public double findMedian() {
        return A.size() != B.size() ? B.peek() : (A.peek() + B.peek()) /2.0;
    }


    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(3);
        System.out.println(medianFinder.findMedian());
    }
}
